// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-06 15:41
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

import java.util.Spliterator;
import java.util.function.Consumer;

public class FindTiltUpdate {
    /**
     * 二叉树总坡度
     */
    int ans = 0;

    /**
     * 计算给定二叉树的根节点的坡度之和
     * 应该实时记录左右子树之和以及左右子树以及根节点之和
     */

    public int findTilt(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getTilt(root)[0] + ans;
    }

    /**
     * 自底向上，保留左右子树的差以及左右子树和根子树的节点之和
     *
     * @param root 传入节点
     * @return result
     */
    private int[] getTilt(TreeNode root) {
        if (root == null) {
            // 空节点 -> 子树和和差都为0
            return new int[]{0, 0};
        }
        if (isLeaf(root)) {
            // 当前节点为叶子节点,子树节点差为0，和为根节点值
            return new int[]{0, root.val};
        }
        // 当前节点不为叶子节点
        int[] lTilt = getTilt(root.left);
        int[] rTilt = getTilt(root.right);
        ans += lTilt[0];
        ans += rTilt[0];
        return new int[]{Math.abs(lTilt[1] - rTilt[1]), lTilt[1] + rTilt[1] + root.val};
    }

    /**
     * 判断当前节点是否为叶子节点
     *
     * @param root 传入的节点
     * @return 是否为叶子节点
     */
    private boolean isLeaf(TreeNode root) {
        if (root == null) {
            return false;
        }
        return root.left == null && root.right == null;
    }

    @Test
    public void shout() {
        int[] nodes = {21, 7, 14, 1, 1, 2, 2, 3, 3};
        Utils utils = new Utils();
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(new FindTiltUpdate().findTilt(root));
        Spliterator<Integer> sp = new Spliterator<Integer>() {
            @Override
            public boolean tryAdvance(Consumer action) {
                return false;
            }

            @Override
            public Spliterator trySplit() {
                return null;
            }

            @Override
            public long estimateSize() {
                return 0;
            }

            @Override
            public int characteristics() {
                return 0;
            }
        };

    }


}
